package com.cuz.daileetcode.bat100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class 存在依赖的任务完成需要的时间 {

    public static void main(String[] args) {
        //             0, 1,  2, 3
        int[] times = {1, 3, 2, 4};
        int[][] dependence = {};
        System.out.println(Arrays.toString(solution1(times, dependence)));
    }

    /***
     * dependence[i]={a,b} 表示a依赖于b任务完成
     * times[i] i任务需要花费times[i] 时间
     * @param times
     * @param dependence
     * @return 每一个任务啥时候可以完成
     */
    public static int[] solution1(int[] times, int[][] dependence) {
        if (times == null || times.length == 0) {
            return times;
        }
        if (dependence == null || dependence.length == 0) {
            return times;
        }
        ArrayList<ArrayList<Integer>> map = new ArrayList<>();
        for (int i = 0; i < times.length; i++) {
            map.add(new ArrayList<>());
        }
        //每一个任务的入度
        int[] entry = new int[times.length];
        //dependence[i]={a,b} 表示a依赖于b任务完成  是一个有向图
        //b->a
        //初始化map
        //dependence={{1，2}，{1，3}，{2，4}}
        //4->2->1
        //3->1
        //map=[,{2,3},{4} ]
        for (int[] loop : dependence) {
            //表示loop[0] 依赖于loop[1]
            map.get(loop[1]).add(loop[0]);
            //loop[0] 依赖于loop[1] 入度++
            entry[loop[0]]++;
        }
        //入度为0的任务执行队列
        LinkedList<Integer> entry0 = new LinkedList<>();
        //初始化入度为0的队列
        for (int i = 0; i < entry.length; i++) {
            //如果这个任务入度为0 表示不依赖于其他任务的执行 那么放到队列 准备执行
            if (entry[i] == 0) {
                entry0.addLast(i);
            }
        }
        //每一个任务结束时间
        int[] eachTaskEndTime = new int[times.length];
        //每一个任务开始时间
        int[] eachTaskStartTime = new int[times.length];
        while (!entry0.isEmpty()) {
            //当前可以执行的任务下表
            Integer curTaskIndex = entry0.removeFirst();
            //花费的时间
            int timeSpend = times[curTaskIndex];
            //开始时间
            int startTime = eachTaskStartTime[curTaskIndex];
            //结束时间
            int endTime = startTime + timeSpend;
            eachTaskEndTime[curTaskIndex] = endTime;
            //当前任务完成被影响到的任务
            ArrayList<Integer> tasksAffected = map.get(curTaskIndex);
            for (Integer taskIndex : tasksAffected) {
                //后置任务入度--
                entry[taskIndex]--;
                //入度为0 那么加到队列末尾 表示这个任务可以执行
                if (entry[taskIndex] == 0) {
                    entry0.addLast(taskIndex);
                }
                //后续任务的启动时间取前置任务最大值
                eachTaskStartTime[taskIndex] = Math.max(eachTaskStartTime[taskIndex], endTime);
            }
        }
        return eachTaskEndTime;
    }
}
